//
// Created by hay boy on 2022/6/17.
//
#ifndef ALGORITHMS_CHAINNODE_CPP
#define ALGORITHMS_CHAINNODE_CPP
#include "ChainNode.h"

template<class T>
Chain<T>::Chain(int initialCapacity) {
    if(initialCapacity<1){
        ostringstream s;
        s<<"Initial capacity = "<<initialCapacity<<" must be > 0";
        throw illegalParameterValue(s.str());
    }
    firstNode = nullptr;
    listSize = 0;
}

template<class T>
Chain<T>::Chain(const Chain<T> & theList) {
    listSize = theList.listSize;
    if(listSize==0){
        firstNode=nullptr;
        return;
    }
    ChainNode<T>* sourceNode = theList.firstNode;
    firstNode = new ChainNode<T>(sourceNode->element);
    sourceNode = sourceNode->next;
    ChainNode<T>* targetNode = firstNode;
    while(sourceNode!=nullptr){
        targetNode->next = new ChainNode<T>(sourceNode->element);
        targetNode = targetNode->next;
        sourceNode = sourceNode->next;
    }
    targetNode->next = nullptr;
}

template<class T>
Chain<T>::~Chain() {
    while(firstNode!=nullptr){
        ChainNode<T>* nextNode = firstNode->next;
        delete firstNode;
        firstNode = nextNode;
    }
}

template<class T>
T &Chain<T>::get(int theIndex) const {
    checkIndex(theIndex);
    ChainNode<T>* currentNode = firstNode;
    for(int i = 0;i<theIndex;i++){
        currentNode = currentNode->next;
    }
    return currentNode->element;
}

template<class T>
int Chain<T>::indexOf(const T &theElement) const {
    ChainNode<T>* currentNode = firstNode;
    int index = 0;
    while(currentNode!=nullptr&&(*currentNode).element!=theElement){
        currentNode = currentNode->next;
        index++;
    }
    if(currentNode==nullptr){
        return -1;
    }else{
        return index;
    }
}

template<class T>
void Chain<T>::erase(int theIndex) {
    checkIndex(theIndex);
    ChainNode<T>* deleteNode;
    if(theIndex==0){
        deleteNode = firstNode;
        firstNode = firstNode->next;
    }else{
        ChainNode<T>* p = firstNode;
        for(int i = 0;i<theIndex-1;i++){
            p = p->next;
        }
        deleteNode = p->next;
        p->next = p->next->next;
    }
    listSize--;
    delete deleteNode;
}

template<class T>
void Chain<T>::insert(int theIndex, const T &theElement) {
    if(theIndex<0||theIndex>listSize){
        ostringstream s;
        s<<"index = "<<theIndex<<" size = "<<listSize;
        throw illegalIndex(s.str());
    }
    if(theIndex==0){
        firstNode = new ChainNode<T>(theElement,firstNode);
    }else{
        ChainNode<T>* p = firstNode;
        for(int i = 0;i<theIndex-1;i++){
            p = p->next;
        }
        p->next = new ChainNode<T>(theElement,p->next);
    }
    listSize++;
}

template<class T>
void Chain<T>::output(ostream &out) const {
    for(ChainNode<T>* currentNode = firstNode;currentNode!=nullptr;currentNode=currentNode->next){
        out<<currentNode->element<<" ";
    }
}

template<class T>
void Chain<T>::checkIndex(int theIndex) const {
    if(theIndex<0||theIndex>=listSize){
        ostringstream s;
        s<<"index = "<<theIndex<<" size = "<<listSize;
        throw illegalIndex(s.str());
    }
}

template<class T>
void Chain<T>::binSort(int range) {
    ChainNode<T>** bottom;
    ChainNode<T>** top;
    bottom = new ChainNode<T>*[range+1];
    top = new ChainNode<T>*[range+1];
    for(int b = 0;b<=range;b++){
        bottom[b] = nullptr;
    }
    for(;firstNode!=nullptr;firstNode=firstNode->next){
        int theBin = firstNode->element;
        if(bottom[theBin]==nullptr){
            bottom[theBin] = top[theBin] = firstNode;
        }else{
            top[theBin]->next = firstNode;
            top[theBin] = firstNode;
        }
    }
    ChainNode<T> *y = nullptr;
    for(int theBin=0;theBin<=range;theBin++){
        if(bottom[theBin]!=nullptr){
            if(y==nullptr){
                firstNode = bottom[theBin];
            }else{
                y->next = bottom[theBin];
            }
            y = top[theBin];
        }
    }
    if(y!=nullptr){
        y->next = nullptr;
    }
    delete[] bottom;
    delete[] top;
}

template<class T>
void Chain<T>::set(int theIndex, const T &theElement) {
    checkIndex(theIndex);
    ChainNode<T>* p = firstNode;
    for(int i = 0;i<theIndex;i++){
        p = p->next;
    }
    p->element = theElement;
}

template<class T>
void Chain<T>::clear() {
    while(Chain<T>::firstNode!=nullptr){
        ChainNode<T>* nextNode = Chain<T>::firstNode->next;
        delete Chain<T>::firstNode;
        Chain<T>::firstNode = nextNode;
    }
    Chain<T>::listSize = 0;
}

#endif
